#pragma once

template < class T >
class CCachedQueue
{
private:
	CHeapPtr<T> m_pCache;
	SIZE_T   m_nCacheLen;
	T *      m_pArray;
	SIZE_T   m_nArrayLen;
	SSIZE_T  m_nRange;
	SSIZE_T  m_nCurr;
	BOOL     m_bCached;
	BOOL     m_bUnderflow;

public:

	CCachedQueue(const LONG_PTR & nRange)
		: m_pArray(NULL), m_nArrayLen(0), 
		  m_nCurr(-nRange), m_nRange(nRange), m_nCacheLen(nRange * 2), 
		  m_bCached(FALSE), m_bUnderflow(TRUE)
	{
		m_pCache.Allocate(m_nCacheLen);
		ASSERT(m_pCache);
	}

	template < class A >
	void Map(A * pArray, SIZE_T nLen)
	{
		ASSERT( m_bUnderflow );

		m_pArray = (T *)pArray;
		m_nArrayLen = nLen * sizeof (A) / sizeof (T);

		if ( !m_bCached )
		{
			for (SIZE_T i = 0; i < m_nCacheLen; i++)
				memcpy(m_pCache + i, m_pArray, sizeof(T));
			m_bCached = TRUE;
		}

		m_bUnderflow = FALSE;
	}

	BOOL Next(void)
	{
		ASSERT( !m_bUnderflow );
		m_nCurr++;

		const SSIZE_T nLimit = m_nArrayLen - m_nRange;

		if ( m_nCurr < nLimit )
			return TRUE;

		memcpy(
			m_pCache, 
			m_pArray + m_nArrayLen - m_nCacheLen, 
			m_nCacheLen * sizeof(T)
			);

		m_nCurr -= m_nArrayLen;
		m_bUnderflow = TRUE;

		return FALSE;
	}
	const T & operator [] (SSIZE_T i) const
	{
		ASSERT(!m_bUnderflow);
		ASSERT(i <= m_nRange && i >= -m_nRange);
		const SSIZE_T nPos = m_nCurr + i;
		return (nPos < 0) ? m_pCache[m_nCacheLen + nPos] : m_pArray[nPos];
	}
	BOOL IsEmpty(void) const
	{
		return m_bUnderflow;
	}

};

